package com.pekExercises;

import java.util.Random;

/**
 * 输入格式：
 * 5 //三角形行数。下面是三角形
 * 7
 * 3 8
 * 8 1 0
 * 2 7 4 4
 * 4 5 2 6 5
 * 要求输出最大和
 *
 * 在上面的数字三角形中寻找一条从顶部到底边的路径，使得
 * 路径上所经过的数字之和最大。路径上的每一步都只能往左下或
 * 右下走。只需要求出这个最大和即可，不必给出具体路径。
 * 三角形的行数大于1小于等于100，数字为 0 - 99
 */
public class NumberPiramid {

    public static int dynamicGetPathFromTopToBottom(int[][] inputArray){

        return dynamicGetPathFromTopToBottomInner(inputArray,0,0);

    }

    private static int dynamicGetPathFromTopToBottomInner(int[][] inputArray, int line, int col) {

        for(int i = inputArray.length - 2;i >= line;i --){

            int[] thisLine = inputArray[i];
            int[] nextLine = inputArray[i + 1];
            for(int j = 0;j < thisLine.length;j ++){
                if(nextLine.length <= j + 1){
                    //thisLine[j] = nextLine[j] + thisLine[j];
                    continue;
                }
                thisLine[j] = Math.max(nextLine[j],nextLine[j + 1]) + thisLine[j];
            }

        }

        return inputArray[line][col];

    }

    public static int getMaxPathFromTopToBottom(int[][] inputArray){
        //初始化tmpInfo
        int[][] tmpInfo = new int[inputArray.length][];
        for(int i = 0;i < inputArray.length;i ++){
            tmpInfo[i] = new int[inputArray[i].length];
            for(int j = 0;j < tmpInfo[i].length;j ++){
                tmpInfo[i][j] = -1;
            }
        }

        return getMaxPathFromTopToBottomInner(inputArray,0,0,tmpInfo);
    }

    private static int getMaxPathFromTopToBottomInner(int[][] inputArray, int line, int col, int[][] tmpInfo) {

        if(line >= inputArray.length - 1){
            if(col >= inputArray[line].length){
                return 0;
            }
            return inputArray[line][col];
        }

        if(col >= inputArray[line].length){
            return 0;
        }

        int max = Integer.MIN_VALUE;
        for(int i = col;i <= col + 1;i ++){
            int tmp;
            if((tmp = tmpInfo[line + 1][i]) != -1){
                tmp += inputArray[line][col];
                if(tmp > max){
                    max = tmp;
                }
                continue;
            }
            tmp = getMaxPathFromTopToBottomInner(inputArray,line + 1,i,tmpInfo);
            tmp += inputArray[line][col];
            if(tmp > max){
                max = tmp;
            }
        }
        tmpInfo[line][col] = max;
        return max;


    }

    public static void main(String[] args){

        int count = 10000;
        int range = 10000;
        Random random = new Random();
        int[][] inputArray = new int[count][count];
        for(int i = 0;i < count;i ++){
            for(int j = 0; j < count;j ++){
                inputArray[i][j] = random.nextInt(range);
            }
        }

        System.out.println("层数"+ count);
        long before = System.currentTimeMillis();
        System.out.println("普通方式:"+getMaxPathFromTopToBottom(inputArray));
        long after = System.currentTimeMillis();

        System.out.println(after - before);

        long before1 = System.currentTimeMillis();
        System.out.println("人人为我:"+dynamicGetPathFromTopToBottom(inputArray));
        long after1 = System.currentTimeMillis();

        System.out.println(after1 - before1);

    }

}
